Codeforces Round #815 (Div. 2)

A

弱智题，交叉相乘判一下倍数关系即可。

Code

#include <cstdio>

long long T, a, b, c, d;

int main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
        a *= d, b *= c;
        if (a == b) puts("0");
        else if (a == 0 || b == 0) puts("1");
        else if (a < b) {
            if (b % a == 0) puts("1");
            else puts("2");
        } else {
            if (a % b == 0) puts("1");
            else puts("2");
        }
    }
}

B

记录整个数组的最大值 $a$ ，次大值 $b$ ，最小值 $c$ ，次小值 $d$ 。容易找到一种划分 $(l,r)$ 使得答案为 $a+b-c-d$ 。显然这是最优的答案。

Code

#include <cstdio>

const int N = 1e5 + 5;

int T, mx1, mx2, mn1, mn2, n, a;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        mx1 = mx2 = 0;
        mn1 = mn2 = 2e9;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a);
            if (a > mx1) mx2 = mx1, mx1 = a;
            else if (a > mx2) mx2 = a;
            if (a < mn1) mn2 = mn1, mn1 = a;
            else if (a < mn2) mn2 = a;
        }
        printf("%lld\n", 1LL * (mx1 + mx2 - mn1 - mn2));
    }
}

C

注意到在一个满足要求的L形里面，有 $2$ 个格子是 $0$ 是最优的消除方式 ，而消除过后又会产生一个新的L形满足要求。

于是我们便可以找到一个有 $2$ 个 $0$ 的L形，从这里开始不断消除，如果找不到只能浪费一些 $1$。

整个方格表扫一遍即可，时间复杂度 $O(nm)$ 。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 505;

int a[N][N], n, m, sum, mn, T;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        sum = 0;
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                scanf("%1d", &a[i][j]);
                sum += a[i][j];
            }
        mn = 0x7fffffff;
        for (int i = 1; i < n; i++)
            for (int j = 1; j < m; j++) {
                int cnt = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
                if (cnt) mn = min(mn, max(1, cnt - 1));
            }
        if (sum == 0) puts("0");
        else printf("%d\n", 1 + sum - mn);
    }
}

D1

考虑dp。设 $f_i$ 为以 $i$ 结尾的最长的合法子序列长度，则有

$f_i=\max\limits_{j<i,\,a_j\oplus i\lt a_i\oplus j}\{f_j+1\}$

朴素转移时间复杂度 $O(n^2)$ ，过不去，怎么办？

考虑缩小 $j$ 的枚举范围。注意到当 $i>j+2^8$ 时，在不考虑二进制下最后 $8$ 位的情况下同样有 $i>j$ 。

由于 $a_i\le 200$ ，所以在 $a_j\oplus i<a_i\oplus j$ 中 $a_i$ 只会对最后 $8$ 位造成影响，所以 $i>j+2^8$ 不会成立，故只需从 $i-2^8$ 枚举即可。

时间复杂度降至 $O(2^8n)$ ，可以通过 D1 。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 3e5 + 5;

inline int read() {
	register int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -f;
		ch = getchar();
	}
	while ('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f == -1 ? -x : x;
}

int a[N], dp[N], n, ans, T;

int main() {
    T = read();
    while (T--) {
        n = read();
        for (int i = 0; i < n; i++) a[i] = read();
        ans = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = max(i - 255, 0); j < i; j++) {
                if ((a[j] ^ i) < (a[i] ^ j))
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
}

D2

待补。

E

待补。